import java.util.Stack;

/**
 * @User: vitobo
 * @Date: 2024-06-20
 * @Description: 栈学习
 *
 *
 * 中缀表达式  转  后缀表达式[逆波兰表达式]
 * 中缀表达式: 操作符位于操作数之间的表达式形式
 * 后缀表达式: 操作符置于操作数之后的表达式表示方法
 *
 *
 * * 1.给一个后缀表达式, 计算其结果? 123 * + 45 * 6 + 7 * +
 *     通过栈, 遇到数字入栈, 遇到运算符 弹出栈顶两个元素, 第一个是右操作数, 第二个是左操作数
 *
 *
 *   2.将递归转为循环(使用栈)
 *
 *
 *   3.括号匹配
 *      字符串遍历完成, 栈也是空的, 此时就是匹配的
 *      字符串没有遍历完成,但是栈空了, 就是右括号多
 *      字符串遍历完成,但是栈不空,此时就是左括号多
 *      当字符串遍历完成了, 但是栈不空,说明左括号还在栈中没有匹配完成
 *
 *   4.逆波兰表达式求值
 *
 *   5.出入栈的顺序,(压入,弹出的顺序是否匹配)
 *
 *   6.最小栈
 *
 *   7.栈,虚拟机栈,栈帧有什么区别?
 *      栈:是一种后进先出的数据结构
 *      虚拟机栈:是JVM中的一块内存空间
 *      栈帧: 是在调用函数的过程当中,在Java虚拟机栈上开辟的一块内存
 *
 *   8.单链表是否可以实现栈???
 *      如果是单链表,头插入栈,时间复杂度为O(1),出栈也是从头出
 *      双向链表也可以实现栈,那么两边都可以入栈和出栈,更加方便 
 *
 *
 *
 */
public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        int x1 = stack.pop();
        System.out.println(x1);

        int x2 = stack.peek();
        System.out.println(x2);

    }


    // 逆波兰表达式求值
    public int evalRPN(String[] tokens){
        Stack<Integer> stack = new Stack<>();

        // 1.遍历tokens数组,判断当中的字符串的类型
        for(String x : tokens){
            if(!isOperations(x)){
                stack.push(Integer.parseInt(x));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x){
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperations(String s){
        if(s.equals("+") || s.equals("-")
                || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }

    // 括号匹配
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 1.判断是不是左括号
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    // 2.遇到了右括号, 但是栈为空,此时不匹配!
                    return false;
                }
                char ch2 = stack.peek();
                // 3.此时,如果满足 这里面的任何一个匹配逻辑, 都是匹配的
                if(ch2 == '(' && ch == ')'
                    || ch2 == '[' && ch == ']'
                    || ch2 == '{' && ch == '}'){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        // 4.当字符串遍历完成了,但是栈不为空,说明左括号还在栈当中没有匹配完成
        if(!stack.empty()){
            return false;
        }
        return true;
    }

    // 出入栈的顺序
    public boolean IsPopOrder(int[] pushA, int[] popA){
        Stack<Integer> stack = new Stack<>();
        // 遍历popA数组
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}
